/*
===========================================================================
Copyright (C) 1999-2005 Id Software, Inc.

This file is part of Quake III Arena source code.

Quake III Arena source code is free software; you can redistribute it
and/or modify it under the terms of the GNU General Public License as
published by the Free Software Foundation; either version 2 of the License,
or (at your option) any later version.

Quake III Arena source code is distributed in the hope that it will be
useful, but WITHOUT ANY WARRANTY; without even the implied warranty of
MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
GNU General Public License for more details.

You should have received a copy of the GNU General Public License
along with Foobar; if not, write to the Free Software
Foundation, Inc., 51 Franklin St, Fifth Floor, Boston, MA  02110-1301  USA
===========================================================================
*/

#include "qbsp.h"


mapDrawSurface_t	mapDrawSurfs[MAX_MAP_DRAW_SURFS];
int			numMapDrawSurfs;

/*
=============================================================================

DRAWSURF CONSTRUCTION

=============================================================================
*/

/*
=================
AllocDrawSurf
=================
*/
mapDrawSurface_t	*AllocDrawSurf( void ) {
	mapDrawSurface_t	*ds;

	if ( numMapDrawSurfs >= MAX_MAP_DRAW_SURFS ) {
		Error( "MAX_MAP_DRAW_SURFS");
	}
	ds = &mapDrawSurfs[ numMapDrawSurfs ];
	numMapDrawSurfs++;

	return ds;
}

/*
=================
DrawSurfaceForSide
=================
*/
#define	SNAP_FLOAT_TO_INT	8
#define	SNAP_INT_TO_FLOAT	(1.0/SNAP_FLOAT_TO_INT)

mapDrawSurface_t	*DrawSurfaceForSide( bspbrush_t *b, side_t *s, winding_t *w ) {
	mapDrawSurface_t	*ds;
	int					i, j;
	shaderInfo_t		*si;
	drawVert_t			*dv;
	float				mins[2], maxs[2];

	// brush primitive :
	// axis base
	vec3_t		texX,texY;
	vec_t		x,y;

	if ( w->numpoints > 64 ) {
		Error( "DrawSurfaceForSide: w->numpoints = %i", w->numpoints );
	}

	si = s->shaderInfo;

	ds = AllocDrawSurf();

	ds->shaderInfo = si;
	ds->mapBrush = b;
	ds->side = s;
	ds->planeNum = s->planenum;
	ds->numVerts = w->numpoints;
	ds->verts = malloc( ds->numVerts * sizeof( *ds->verts ) );
	memset( ds->verts, 0, ds->numVerts * sizeof( *ds->verts ) );

	mins[0] = mins[1] = 99999;
	maxs[0] = maxs[1] = -99999;

	// compute s/t coordinates from brush primitive texture matrix
	// compute axis base
	ComputeAxisBase( mapplanes[s->planenum].normal, texX, texY );

	for ( j = 0 ; j < w->numpoints ; j++ ) {
		dv = ds->verts + j;

		// round the xyz to a given precision
		for ( i = 0 ; i < 3 ; i++ ) {
			dv->xyz[i] = SNAP_INT_TO_FLOAT * floor( w->p[j][i] * SNAP_FLOAT_TO_INT + 0.5 );
		}
	
		if (g_bBrushPrimit==BPRIMIT_OLDBRUSHES)
		{
			// calculate texture s/t
			dv->st[0] = s->vecs[0][3] + DotProduct( s->vecs[0],	dv->xyz );
			dv->st[1] = s->vecs[1][3] + DotProduct( s->vecs[1],	dv->xyz );
			dv->st[0] /= si->width;
			dv->st[1] /= si->height;
		} 
		else
		{
			// calculate texture s/t from brush primitive texture matrix
			x = DotProduct( dv->xyz, texX );
			y = DotProduct( dv->xyz, texY );
			dv->st[0]=s->texMat[0][0]*x+s->texMat[0][1]*y+s->texMat[0][2];
			dv->st[1]=s->texMat[1][0]*x+s->texMat[1][1]*y+s->texMat[1][2];
		}

		for ( i = 0 ; i < 2 ; i++ ) {
			if ( dv->st[i] < mins[i] ) {
				mins[i] = dv->st[i];
			}
			if ( dv->st[i] > maxs[i] ) {
				maxs[i] = dv->st[i];
			}
		}

		// copy normal
		VectorCopy ( mapplanes[s->planenum].normal, dv->normal );
	}

	// adjust the texture coordinates to be as close to 0 as possible
//	if ( !si->globalTexture ) {
		mins[0] = floor( mins[0] );
		mins[1] = floor( mins[1] );
		for ( i = 0 ; i < w->numpoints ; i++ ) {
			dv = ds->verts + i;
			dv->st[0] -= mins[0];
			dv->st[1] -= mins[1];
		}
//	}

	return ds;
}


//=========================================================================




typedef struct {
	int				planenum;
	shaderInfo_t	*shaderInfo;
	int				count;
} sideRef_t;

#define	MAX_SIDE_REFS	MAX_MAP_PLANES

sideRef_t	sideRefs[MAX_SIDE_REFS];
int			numSideRefs;

void AddSideRef( side_t *side ) {
	int		i;

	for ( i = 0 ; i < numSideRefs ; i++ ) {
		if ( side->planenum == sideRefs[i].planenum
			&& side->shaderInfo == sideRefs[i].shaderInfo ) {
			sideRefs[i].count++;
			return;
		}
	}

	if ( numSideRefs == MAX_SIDE_REFS ) {
		Error( "MAX_SIDE_REFS" );
	}

	sideRefs[i].planenum = side->planenum;
	sideRefs[i].shaderInfo = side->shaderInfo;
	sideRefs[i].count++;
	numSideRefs++;
}


/*
=====================
MergeSides

=====================
*/
void MergeSides( entity_t *e, tree_t *tree ) {
	int				i;

	qprintf( "----- MergeSides -----\n");

	for ( i = e->firstDrawSurf ; i < numMapDrawSurfs ; i++ ) {
//			AddSideRef( side );
	}

	qprintf( "%5i siderefs\n", numSideRefs );
}


//===================================================================================

/*
====================
WindingFromDrawSurf
====================
*/
winding_t	*WindingFromDrawSurf( mapDrawSurface_t *ds ) {
	winding_t	*w;
	int			i;

	w = AllocWinding( ds->numVerts );
	w->numpoints = ds->numVerts;
	for ( i = 0 ; i < ds->numVerts ; i++ ) {
		VectorCopy( ds->verts[i].xyz, w->p[i] );
	}
	return w;
}


//=====================================================================

/*
===================
SubdivideDrawSurf
===================
*/
void SubdivideDrawSurf( mapDrawSurface_t *ds, winding_t *w, float subdivisions ) {
	int				i;
	int				axis;
	vec3_t			bounds[2];
	const float		epsilon = 0.1;
	int				subFloor, subCeil;
	winding_t		*frontWinding, *backWinding;
	mapDrawSurface_t	*newds;

	if ( !w ) {
		return;
	}
	if ( w->numpoints < 3 ) {
		Error( "SubdivideDrawSurf: Bad w->numpoints" );
	}

	ClearBounds( bounds[0], bounds[1] );
	for ( i = 0 ; i < w->numpoints ; i++ ) {
		AddPointToBounds( w->p[i], bounds[0], bounds[1] );
	}

	for ( axis = 0 ; axis < 3 ; axis++ ) {
		vec3_t planePoint = { 0, 0, 0 };
		vec3_t planeNormal = { 0, 0, 0 };
		float d;

		subFloor = floor( bounds[0][axis]  / subdivisions ) * subdivisions;
		subCeil = ceil( bounds[1][axis] / subdivisions ) * subdivisions;

		planePoint[axis] = subFloor + subdivisions;
		planeNormal[axis] = -1;

		d = DotProduct( planePoint, planeNormal );

		// subdivide if necessary
		if ( subCeil - subFloor > subdivisions ) {
			// gotta clip polygon into two polygons
			ClipWindingEpsilon( w, planeNormal, d, epsilon, &frontWinding, &backWinding );

			// the clip may not produce two polygons if it was epsilon close
			if ( !frontWinding ) {
				w = backWinding;
			} else if ( !backWinding ) {
				w = frontWinding;
			} else {
				SubdivideDrawSurf( ds, frontWinding, subdivisions );
				SubdivideDrawSurf( ds, backWinding, subdivisions );

				return;
			}
		}
	}

	// emit this polygon
	newds = DrawSurfaceForSide( ds->mapBrush, ds->side, w );
}


/*
=====================
SubdivideDrawSurfs

Chop up surfaces that have subdivision attributes
=====================
*/
void SubdivideDrawSurfs( entity_t *e, tree_t *tree ) {
	int				i;
	mapDrawSurface_t	*ds;
	int				numBaseDrawSurfs;
	winding_t		*w;
	float			subdivision;
	shaderInfo_t	*si;
	int				c_subdiv = 0;

	qprintf( "----- SubdivideDrawSurfs -----\n");
	numBaseDrawSurfs = numMapDrawSurfs;
	for ( i = e->firstDrawSurf ; i < numBaseDrawSurfs ; i++ ) {
		ds = &mapDrawSurfs[i];

		// only subdivide brush sides, not patches or func_statics
		if ( !ds->side ) {
			continue;
		}

		// check subdivision for shader
		si = ds->side->shaderInfo;
		if ( !si ) {
			continue;
		}

		if (ds->shaderInfo->surfaceFlags & SURFACE_DISCRETE) {
			continue;
		}

		subdivision = si->subdivisions;
		if ( !subdivision ) {
			continue;
		}

		w = WindingFromDrawSurf( ds );
		ds->numVerts = 0;		// remove this reference
		SubdivideDrawSurf( ds, w, subdivision );

		c_subdiv++;
	}

	qprintf( "%5i surfaces subdivided\n", c_subdiv);
}


//===================================================================================

/*
====================
ClipSideIntoTree_r

Adds non-opaque leaf fragments to the convex hull
====================
*/
void ClipSideIntoTree_r( winding_t *w, side_t *side, node_t *node ) {
	plane_t			*plane;
	winding_t		*front, *back;

	if ( !w ) {
		return;
	}

	if ( node->planenum != PLANENUM_LEAF ) {
		if ( side->planenum == node->planenum ) {
			ClipSideIntoTree_r( w, side, node->children[0] );
			return;
		}
		if ( side->planenum == ( node->planenum ^ 1) ) {
			ClipSideIntoTree_r( w, side, node->children[1] );
			return;
		}

		plane = &mapplanes[ node->planenum ];
		ClipWindingEpsilon ( w, plane->normal, plane->dist,
				ON_EPSILON, &front, &back );
		FreeWinding( w );

		ClipSideIntoTree_r( front, side, node->children[0] );
		ClipSideIntoTree_r( back, side, node->children[1] );

		return;
	}

	// if opaque leaf, don't add
	if ( !node->opaque ) {
		AddWindingToConvexHull( w, &side->visibleHull, mapplanes[ side->planenum ].normal );
	}

	FreeWinding( w );
	return;
}


/*
=====================
ClipSidesIntoTree

Creates side->visibleHull for all visible sides

The drawsurf for a side will consist of the convex hull of
all points in non-opaque clusters, which allows overlaps
to be trimmed off automatically.
=====================
*/
void ClipSidesIntoTree( entity_t *e, tree_t *tree ) {
	bspbrush_t		*b;
	int				i;
	winding_t		*w;
	side_t			*side, *newSide;
	shaderInfo_t	*si;

	qprintf( "----- ClipSidesIntoTree -----\n");

	for ( b = e->brushes ; b ; b = b->next ) {
		for ( i = 0 ; i < b->numsides ; i++ ) {
			side = &b->sides[i];
			if ( !side->winding) {
				continue;
			}
			w = CopyWinding( side->winding );
			side->visibleHull = NULL;
			ClipSideIntoTree_r( w, side, tree->headnode );

			w = side->visibleHull;
			if ( !w ) {
				continue;
			}
			si = side->shaderInfo;
			if ( !si ) {
				continue;
			}
			// don't create faces for non-visible sides
			if ( si->surfaceFlags & SURFACE_NODRAW ) {
				continue;
			}

			// always use the original quad winding for discrete surfaces
			if ( side->shaderInfo->surfaceFlags & SURFACE_DISCRETE ) {
				w = side->winding;
			}
			//
			if ( side->bevel ) {
				Error( "monkey tried to create draw surface for brush bevel" );
			}
			// save this winding as a visible surface
			DrawSurfaceForSide( b, side, w );

			// make a back side for it if needed
			if ( !si->backMaterial[0] ) {
				continue;
			}

			// duplicate the side
			w = ReverseWinding( w );
		
			newSide = malloc( sizeof( *side ) );
			*newSide = *side;
			newSide->visibleHull = w;
			newSide->planenum ^= 1;
			newSide->shaderInfo = ShaderInfoForShader(si->backMaterial);

			// save this winding as a visible surface
			DrawSurfaceForSide( b, newSide, w );
		}
	}
}

/*
===================================================================================

  FILTER REFERENCES DOWN THE TREE

===================================================================================
*/

/*
====================
FilterDrawSurfIntoTree

Place a reference to the given drawsurf in every leaf it contacts
We assume that the point mesh aproximation to the curve will get a 
reference into all the leafs we need.
====================
*/
int FilterMapDrawSurfIntoTree( vec3_t point, mapDrawSurface_t *ds, node_t *node ) {
	drawSurfRef_t	*dsr;
	float			d;
	plane_t			*plane;
	int				c;

	if ( node->planenum != PLANENUM_LEAF ) {
		plane = &mapplanes[ node->planenum ];
		d = DotProduct( point, plane->normal ) - plane->dist;
		c = 0;
		if ( d >= -ON_EPSILON ) {
			c += FilterMapDrawSurfIntoTree( point, ds, node->children[0] );
		}
		if ( d <= ON_EPSILON ) {
			c += FilterMapDrawSurfIntoTree( point, ds, node->children[1] );
		}
		return c;
	}

	// if opaque leaf, don't add
	if ( node->opaque ) {
		return 0;
	}

	// add the drawsurf if it hasn't been already
	for ( dsr = node->drawSurfReferences ; dsr ; dsr = dsr->nextRef ) {
		if ( dsr->outputNumber == numDrawSurfaces ) {
			return 0;		// already referenced
		}
	}

	dsr = malloc( sizeof( *dsr ) );
	dsr->outputNumber = numDrawSurfaces;
	dsr->nextRef = node->drawSurfReferences;
	node->drawSurfReferences = dsr;
	return 1;
}

/*
====================
FilterDrawSurfIntoTree_r

Place a reference to the given drawsurf in every leaf it is in
====================
*/
int FilterMapDrawSurfIntoTree_r( winding_t *w, mapDrawSurface_t *ds, node_t *node ) {
	drawSurfRef_t	*dsr;
	plane_t			*plane;
	int				total;
	winding_t		*front, *back;

	if ( node->planenum != PLANENUM_LEAF ) {
		plane = &mapplanes[ node->planenum ];
		ClipWindingEpsilon ( w, plane->normal, plane->dist,
				ON_EPSILON, &front, &back );

		total = 0;
		if ( front ) {
			total += FilterMapDrawSurfIntoTree_r( front, ds, node->children[0] );
		}
		if ( back ) {
			total += FilterMapDrawSurfIntoTree_r( back, ds, node->children[1] );
		}

		FreeWinding( w );
		return total;
	}

	// if opaque leaf, don't add
	if ( node->opaque ) {
		return 0;
	}

	// add the drawsurf if it hasn't been already
	for ( dsr = node->drawSurfReferences ; dsr ; dsr = dsr->nextRef ) {
		if ( dsr->outputNumber == numDrawSurfaces ) {
			return 0;		// already referenced
		}
	}

	dsr = malloc( sizeof( *dsr ) );
	dsr->outputNumber = numDrawSurfaces;
	dsr->nextRef = node->drawSurfReferences;
	node->drawSurfReferences = dsr;
	return 1;
}

/*
====================
FilterSideIntoTree_r

Place a reference to the given drawsurf in every leaf it contacts
====================
*/
int FilterSideIntoTree_r( winding_t *w, side_t *side, mapDrawSurface_t *ds, node_t *node ) {
	drawSurfRef_t	*dsr;
	plane_t			*plane;
	winding_t		*front, *back;
	int				total;

	if ( !w ) {
		return 0;
	}

	if ( node->planenum != PLANENUM_LEAF ) {
		if ( side->planenum == node->planenum ) {
			return FilterSideIntoTree_r( w, side, ds, node->children[0] );
		}
		if ( side->planenum == ( node->planenum ^ 1) ) {
			return FilterSideIntoTree_r( w, side, ds, node->children[1] );
		}

		plane = &mapplanes[ node->planenum ];
		ClipWindingEpsilon ( w, plane->normal, plane->dist,
				ON_EPSILON, &front, &back );

		total = FilterSideIntoTree_r( front, side, ds, node->children[0] );
		total += FilterSideIntoTree_r( back, side, ds, node->children[1] );

		FreeWinding( w );
		return total;
	}

	// if opaque leaf, don't add
	if ( node->opaque ) {
		return 0;
	}

	dsr = malloc( sizeof( *dsr ) );
	dsr->outputNumber = numDrawSurfaces;
	dsr->nextRef = node->drawSurfReferences;
	node->drawSurfReferences = dsr;

	FreeWinding( w );
	return 1;
}


/*
=====================
FilterFaceIntoTree
=====================
*/
int	FilterFaceIntoTree( mapDrawSurface_t *ds, tree_t *tree ) {
	int			l;
	winding_t	*w;

	w = WindingFromDrawSurf( ds );
	l = FilterSideIntoTree_r( w, ds->side, ds, tree->headnode );

	return l;
}



/*
=====================
FilterPatchSurfIntoTree
=====================
*/
int FilterPatchSurfIntoTree( mapDrawSurface_t *ds, tree_t *tree ) {

	int					i;
	int					l;
	winding_t			*w;
	srfGridMesh_t		*grid = ds->grid;
	int					width, height;
	int					index[6];

	l = 0;
	for (height = 0; height < grid->height - 1; height++){
		for (width = 0; width < grid->width - 1; width++){
			i = height * grid->width + width;

			index[0] = i;
			index[1] = i + grid->width;
			index[2] = i + 1;

			index[3] = i + 1;
			index[4] = i + grid->width;
			index[5] = i + grid->width + 1;

			w = AllocWinding(3);
			VectorCopy(grid->verts[index[0]].xyz, w->p[0]);
			VectorCopy(grid->verts[index[1]].xyz, w->p[1]);
			VectorCopy(grid->verts[index[2]].xyz, w->p[2]);
			w->numpoints = 3;
			l += FilterMapDrawSurfIntoTree_r( w, ds, tree->headnode );

			w = AllocWinding(3);
			VectorCopy(grid->verts[index[3]].xyz, w->p[0]);
			VectorCopy(grid->verts[index[4]].xyz, w->p[1]);
			VectorCopy(grid->verts[index[5]].xyz, w->p[2]);
			w->numpoints = 3;
			l += FilterMapDrawSurfIntoTree_r( w, ds, tree->headnode );
		}
	}

	// also use the old point filtering into the tree
	for ( i = 0 ; i < grid->width * grid->height ; i++ ) {
		l += FilterMapDrawSurfIntoTree( grid->verts[i].xyz, ds, tree->headnode );
	}

	return l;
}


/*
=====================
FilterMiscModelSurfIntoTree
=====================
*/
int	FilterMiscModelSurfIntoTree( mapDrawSurface_t *ds, tree_t *tree ) {
	int			i;
	int			l;
	winding_t *w;

	l = 0;
	for (i = 0; i < ds->numIndexes; i += 3 ) {
		w = AllocWinding(3);
		VectorCopy(ds->verts[ds->indexes[i+0]].xyz, w->p[0]);
		VectorCopy(ds->verts[ds->indexes[i+1]].xyz, w->p[1]);
		VectorCopy(ds->verts[ds->indexes[i+2]].xyz, w->p[2]);
		w->numpoints = 3;
		l += FilterMapDrawSurfIntoTree_r( w, ds, tree->headnode );
	}

	// also use the old point filtering into the tree
	for ( i = 0 ; i < ds->numVerts ; i++ ) {
		l += FilterMapDrawSurfIntoTree( ds->verts[i].xyz, ds, tree->headnode );
	}

	return l;
}

/*
=====================
FilterFoliageSurfIntoTree
=====================
*/
int FilterFoliageSurfIntoTree (mapDrawSurface_t *ds, tree_t *tree){

	dfoliage_t			*f;
	winding_t			*w;
	int					*indices;
	drawVertNew_t		*vertices;
	vec3_t				axis[3];
	vec3_t				point;
	int					i, j;
	int					l;

	indices = &drawIndexes[ds->foliageIndex];
	vertices = &drawVerts[ds->foliageVertex];

	l = 0;
	for (i = 0; i < ds->numFoliages; i++){
		f = &foliages[ds->firstFoliage+i];

		AnglesToAxis(f->angles, axis);

		for (j = 0; j < ds->numIndexes; j += 3){
			w = AllocWinding(3);

			w->p[0][0] = DotProduct(vertices[indices[j+0]].xyz, axis[0]) + f->origin[0];
			w->p[0][1] = DotProduct(vertices[indices[j+0]].xyz, axis[1]) + f->origin[1];
			w->p[0][2] = DotProduct(vertices[indices[j+0]].xyz, axis[2]) + f->origin[2];

			w->p[1][0] = DotProduct(vertices[indices[j+1]].xyz, axis[0]) + f->origin[0];
			w->p[1][1] = DotProduct(vertices[indices[j+1]].xyz, axis[1]) + f->origin[1];
			w->p[1][2] = DotProduct(vertices[indices[j+1]].xyz, axis[2]) + f->origin[2];

			w->p[2][0] = DotProduct(vertices[indices[j+2]].xyz, axis[0]) + f->origin[0];
			w->p[2][1] = DotProduct(vertices[indices[j+2]].xyz, axis[1]) + f->origin[1];
			w->p[2][2] = DotProduct(vertices[indices[j+2]].xyz, axis[2]) + f->origin[2];

			w->numpoints = 3;
			l += FilterMapDrawSurfIntoTree_r(w, ds, tree->headnode);
		}
	}

	// Also use the old point filtering into the tree
	for (i = 0; i < ds->numFoliages; i++){
		f = &foliages[ds->firstFoliage+i];

		AnglesToAxis(f->angles, axis);

		for (j = 0; j < ds->numVerts; j++){
			point[0] = DotProduct(vertices[j].xyz, axis[0]) + f->origin[0];
			point[1] = DotProduct(vertices[j].xyz, axis[1]) + f->origin[1];
			point[2] = DotProduct(vertices[j].xyz, axis[2]) + f->origin[2];

			l += FilterMapDrawSurfIntoTree(point, ds, tree->headnode);
		}
	}

	return l;
}

/*
====================
FilterDrawSurfBoundsIntoTree

Place a reference to the given drawsurf in every leaf it contacts
====================
*/
int BoundsOnSide (plane_t *plane, vec3_t mins, vec3_t maxs){

	float	d1, d2;
	int		signBits = 0;

	if (plane->normal[0] < 0.0f)
		signBits |= 1;
	if (plane->normal[1] < 0.0f)
		signBits |= 2;
	if (plane->normal[2] < 0.0f)
		signBits |= 4;

	switch (signBits){
	case 0:
		d1 = plane->normal[0] * maxs[0] + plane->normal[1] * maxs[1] + plane->normal[2] * maxs[2];
		d2 = plane->normal[0] * mins[0] + plane->normal[1] * mins[1] + plane->normal[2] * mins[2];
		break;
	case 1:
		d1 = plane->normal[0] * mins[0] + plane->normal[1] * maxs[1] + plane->normal[2] * maxs[2];
		d2 = plane->normal[0] * maxs[0] + plane->normal[1] * mins[1] + plane->normal[2] * mins[2];
		break;
	case 2:
		d1 = plane->normal[0] * maxs[0] + plane->normal[1] * mins[1] + plane->normal[2] * maxs[2];
		d2 = plane->normal[0] * mins[0] + plane->normal[1] * maxs[1] + plane->normal[2] * mins[2];
		break;
	case 3:
		d1 = plane->normal[0] * mins[0] + plane->normal[1] * mins[1] + plane->normal[2] * maxs[2];
		d2 = plane->normal[0] * maxs[0] + plane->normal[1] * maxs[1] + plane->normal[2] * mins[2];
		break;
	case 4:
		d1 = plane->normal[0] * maxs[0] + plane->normal[1] * maxs[1] + plane->normal[2] * mins[2];
		d2 = plane->normal[0] * mins[0] + plane->normal[1] * mins[1] + plane->normal[2] * maxs[2];
		break;
	case 5:
		d1 = plane->normal[0] * mins[0] + plane->normal[1] * maxs[1] + plane->normal[2] * mins[2];
		d2 = plane->normal[0] * maxs[0] + plane->normal[1] * mins[1] + plane->normal[2] * maxs[2];
		break;
	case 6:
		d1 = plane->normal[0] * maxs[0] + plane->normal[1] * mins[1] + plane->normal[2] * mins[2];
		d2 = plane->normal[0] * mins[0] + plane->normal[1] * maxs[1] + plane->normal[2] * maxs[2];
		break;
	case 7:
		d1 = plane->normal[0] * mins[0] + plane->normal[1] * mins[1] + plane->normal[2] * mins[2];
		d2 = plane->normal[0] * maxs[0] + plane->normal[1] * maxs[1] + plane->normal[2] * maxs[2];
		break;
	default:
		d1 = 0.0;
		d2 = 0.0;
		break;
	}

	if (d2 < plane->dist){
		if (d1 >= plane->dist)
			return SIDE_CROSS;
		else
			return SIDE_BACK;
	}

	return SIDE_FRONT;
}

int FilterDrawSurfBoundsIntoTree( vec3_t mins, vec3_t maxs, mapDrawSurface_t *ds, node_t *node ) {
	drawSurfRef_t	*dsr;
	plane_t			*plane;
	int				c, side;

	if ( node->planenum != PLANENUM_LEAF ) {
		plane = &mapplanes[ node->planenum ];

		side = BoundsOnSide(plane, mins, maxs);

		c = 0;
		if ( side == SIDE_FRONT ) {
			return FilterDrawSurfBoundsIntoTree( mins, maxs, ds, node->children[0] );
		}
		if ( side == SIDE_BACK ) {
			return FilterDrawSurfBoundsIntoTree( mins, maxs, ds, node->children[1] );
		}

		c += FilterDrawSurfBoundsIntoTree( mins, maxs, ds, node->children[0] );
		c += FilterDrawSurfBoundsIntoTree( mins, maxs, ds, node->children[1] );

		return c;
	}

	// if opaque leaf, don't add
	if ( node->opaque ) {
		return 0;
	}

	// add the drawsurf if it hasn't been already
	for ( dsr = node->drawSurfReferences ; dsr ; dsr = dsr->nextRef ) {
		if ( dsr->outputNumber == numDrawSurfaces - 1 ) {
			return 0;		// already referenced
		}
	}

	dsr = malloc( sizeof( *dsr ) );
	dsr->outputNumber = numDrawSurfaces - 1;
	dsr->nextRef = node->drawSurfReferences;
	node->drawSurfReferences = dsr;
	return 1;
}



//======================================================================

int		c_stripSurfaces, c_fanSurfaces;






/*
 =================
 CalcSurfaceBounds

 Fills in surface mins/maxs
 =================
*/
void CalcSurfaceBounds (dsurface_t *surf){

	drawVertNew_t	*dv;
	int			i;

	ClearBounds(surf->mins, surf->maxs);

	for (i = 0, dv = &drawVerts[surf->firstVert]; i < surf->numVerts; i++, dv++)
		AddPointToBounds(dv->xyz, surf->mins, surf->maxs);
}

/*
 =================
 DeformSurfaceBounds

 Ugly hack for culling
 =================
*/
void DeformSurfaceBounds (dsurface_t *surf, deform_t deform, float size){

	drawVertNew_t	*v;
	vec3_t			center, vecs[3];
	float			radius;
	float			length[3], shortest;

	if (deform == DFRM_NONE)
		return;

	switch (deform){
	case DFRM_EXPAND:
	case DFRM_MOVE:
	case DFRM_FLARE:
		// Just expand the bounds
		if (size <= 0.0f)
			break;

		surf->mins[0] -= size;
		surf->mins[1] -= size;
		surf->mins[2] -= size;

		surf->maxs[0] += size;
		surf->maxs[1] += size;
		surf->maxs[2] += size;

		break;
	case DFRM_SPRITE:
		// Find the approximate radius of the sprite
		radius = RadiusFromBounds(surf->mins, surf->maxs);

		center[0] = (surf->mins[0] + surf->maxs[0]) * 0.5f;
		center[1] = (surf->mins[1] + surf->maxs[1]) * 0.5f;
		center[2] = (surf->mins[2] + surf->maxs[2]) * 0.5f;

		surf->mins[0] = center[0] - radius;
		surf->mins[1] = center[1] - radius;
		surf->mins[2] = center[2] - radius;
		surf->maxs[0] = center[0] + radius;
		surf->maxs[1] = center[1] + radius;
		surf->maxs[2] = center[2] + radius;

		break;
	case DFRM_TUBE:
		// Find the shortest axis, then expand the bounds
		v = &drawVerts[surf->firstVert];

		VectorSubtract(v[1].xyz, v[0].xyz, vecs[0]);
		VectorSubtract(v[2].xyz, v[0].xyz, vecs[1]);
		VectorSubtract(v[2].xyz, v[1].xyz, vecs[2]);

		length[0] = VectorLength(vecs[0]);
		length[1] = VectorLength(vecs[1]);
		length[2] = VectorLength(vecs[2]);

		shortest = length[0];
		if (length[1] < shortest)
			shortest = length[1];
		if (length[2] < shortest)
			shortest = length[2];

		shortest *= 0.5f;		// Half the length

		surf->mins[0] -= shortest;
		surf->mins[1] -= shortest;
		surf->mins[2] -= shortest;
		surf->maxs[0] += shortest;
		surf->maxs[1] += shortest;
		surf->maxs[2] += shortest;

		break;
	}
}

/*
 =================
 FindSurfaceTriangleWithEdge
 =================
*/
static int FindSurfaceTriangleWithEdge (int numTriangles, int *indices, int start, int end, int ignore){

	int		*index;
	int		count, match;
	int		i;

	count = 0;
	match = numTriangles;

	for (i = 0, index = indices; i < numTriangles; i++, index += 3){
		if ((index[0] == start && index[1] == end) || (index[1] == start && index[2] == end) || (index[2] == start && index[0] == end)){
			if (i != ignore)
				match = i;

			count++;
		}
		else if ((index[1] == start && index[0] == end) || (index[2] == start && index[1] == end) || (index[0] == start && index[2] == end))
			count++;
	}

	// Detect edges shared by three triangles and make them seams
	if (count > 2)
		match = numTriangles;

	return match;
}

/*
 =================
 BuildSurfaceTriangleNeighbors
 =================
*/
void BuildSurfaceTriangleNeighbors (int numTriangles, int *indices, int *neighbors){

	int		*index, *neighbor;
	int		i;
	
	for (i = 0, index = indices, neighbor = neighbors; i < numTriangles; i++, index += 3, neighbor += 3){
		neighbor[0] = FindSurfaceTriangleWithEdge(numTriangles, indices, index[1], index[0], i);
		neighbor[1] = FindSurfaceTriangleWithEdge(numTriangles, indices, index[2], index[1], i);
		neighbor[2] = FindSurfaceTriangleWithEdge(numTriangles, indices, index[0], index[2], i);
	}
}

/*
 =================
 CalcSurfaceTangentVectors
 =================
*/
void CalcSurfaceTangentVectors (int numIndices, int *indices, int numVertices, drawVertNew_t *vertices){

	int			*index;
	drawVertNew_t	*vertex;
	float		*pXyz[3], *pSt[3];
	float		edge[2][5];
	vec3_t		normal, tangents[2], cross;
	float		d;
	int			i, j;

	// Clear
	for (i = 0, vertex = vertices; i < numVertices; i++, vertex++){
		VectorClear(vertex->normal);
		VectorClear(vertex->tangents[0]);
		VectorClear(vertex->tangents[1]);
	}

	// Calculate normal and tangent vectors
	for (i = 0, index = indices; i < numIndices; i += 3, index += 3){
		pXyz[0] = (float *)(vertices[index[0]].xyz);
		pXyz[1] = (float *)(vertices[index[1]].xyz);
		pXyz[2] = (float *)(vertices[index[2]].xyz);

		pSt[0] = (float *)(vertices[index[0]].st);
		pSt[1] = (float *)(vertices[index[1]].st);
		pSt[2] = (float *)(vertices[index[2]].st);

		// Find edges
		edge[0][0] = pXyz[1][0] - pXyz[0][0];
		edge[0][1] = pXyz[1][1] - pXyz[0][1];
		edge[0][2] = pXyz[1][2] - pXyz[0][2];
		edge[0][3] = pSt[1][0] - pSt[0][0];
		edge[0][4] = pSt[1][1] - pSt[0][1];

		edge[1][0] = pXyz[2][0] - pXyz[0][0];
		edge[1][1] = pXyz[2][1] - pXyz[0][1];
		edge[1][2] = pXyz[2][2] - pXyz[0][2];
		edge[1][3] = pSt[2][0] - pSt[0][0];
		edge[1][4] = pSt[2][1] - pSt[0][1];

		// Compute normal vector
		normal[0] = edge[1][1] * edge[0][2] - edge[1][2] * edge[0][1];
		normal[1] = edge[1][2] * edge[0][0] - edge[1][0] * edge[0][2];
		normal[2] = edge[1][0] * edge[0][1] - edge[1][1] * edge[0][0];

		VectorNormalize(normal, normal);

		// Compute first tangent vector
		tangents[0][0] = edge[1][4] * edge[0][0] - edge[1][0] * edge[0][4];
		tangents[0][1] = edge[1][4] * edge[0][1] - edge[1][1] * edge[0][4];
		tangents[0][2] = edge[1][4] * edge[0][2] - edge[1][2] * edge[0][4];

		VectorNormalize(tangents[0], tangents[0]);

		// Compute second tangent vector
		tangents[1][0] = edge[1][0] * edge[0][3] - edge[1][3] * edge[0][0];
		tangents[1][1] = edge[1][1] * edge[0][3] - edge[1][3] * edge[0][1];
		tangents[1][2] = edge[1][2] * edge[0][3] - edge[1][3] * edge[0][2];

		VectorNormalize(tangents[1], tangents[1]);

		// Inverse tangent vectors if needed
		CrossProduct(tangents[1], tangents[0], cross);
		if (DotProduct(cross, normal) < 0.0f){
			VectorInverse(tangents[0]);
			VectorInverse(tangents[1]);
		}

		// Add the vectors
		for (j = 0; j < 3; j++){
			VectorAdd(vertices[index[j]].normal, normal, vertices[index[j]].normal);
			VectorAdd(vertices[index[j]].tangents[0], tangents[0], vertices[index[j]].tangents[0]);
			VectorAdd(vertices[index[j]].tangents[1], tangents[1], vertices[index[j]].tangents[1]);
		}
	}

	// Renormalize
	for (i = 0, vertex = vertices; i < numVertices; i++, vertex++){
		VectorNormalize(vertex->normal, vertex->normal);

		d = DotProduct(vertex->tangents[0], vertex->normal);
		VectorMA(vertex->tangents[0], -d, vertex->normal, vertex->tangents[0]);
		VectorNormalize(vertex->tangents[0], vertex->tangents[0]);

		d = DotProduct(vertex->tangents[1], vertex->normal);
		VectorMA(vertex->tangents[1], -d, vertex->normal, vertex->tangents[1]);
		VectorNormalize(vertex->tangents[1], vertex->tangents[1]);
	}
}

/*
 =================
 CalcSurfaceFacePlanes
 =================
*/
void CalcSurfaceFacePlanes (int numTriangles, int *indices, dplane_t *facePlanes, drawVertNew_t *vertices){

	int			*index;
	dplane_t	*facePlane;
	float		*pXyz[3];
	vec3_t		edge[2];
	int			i;

	// Calculate face planes
	for (i = 0, index = indices, facePlane = facePlanes; i < numTriangles; i++, index += 3, facePlane++){
		pXyz[0] = (float *)(vertices[index[0]].xyz);
		pXyz[1] = (float *)(vertices[index[1]].xyz);
		pXyz[2] = (float *)(vertices[index[2]].xyz);

		// Find edges
		VectorSubtract(pXyz[1], pXyz[0], edge[0]);
		VectorSubtract(pXyz[2], pXyz[0], edge[1]);

		// Compute normal
		CrossProduct(edge[1], edge[0], facePlane->normal);
		VectorNormalize(facePlane->normal, facePlane->normal);

		// Compute distance
		facePlane->dist = DotProduct(pXyz[0], facePlane->normal);
	}
}

void EmitDrawIndexes( mapDrawSurface_t *ds, dsurface_t *out )
{
	int			i;
	
	out->firstIndex = numDrawIndexes;
	out->numIndexes = ds->numIndexes;

	for (i = 0; i < ds->numIndexes; i++){
		if (numDrawIndexes == MAX_MAP_DRAW_INDEXES)
			Error("MAX_MAP_DRAW_INDEXES");

		drawIndexes[numDrawIndexes++] = ds->indexes[i];
	}

	// Compute neighbors
	out->firstNeighbor = out->firstIndex;

	if (numDrawNeighbors + out->numIndexes > MAX_MAP_DRAW_NEIGHBORS)
		Error("MAX_MAP_DRAW_NEIGHBORS");

	BuildSurfaceTriangleNeighbors(out->numIndexes / 3, &drawIndexes[out->firstIndex], &drawNeighbors[out->firstNeighbor]);
	numDrawNeighbors += out->numIndexes;
}


/*
==================
IsTriangleDegenerate

Returns qtrue if all three points are collinear or backwards
===================
*/
#define	COLINEAR_AREA	10
static qboolean	IsTriangleDegenerate( drawVertNew_t *points, int a, int b, int c ) {
	vec3_t		v1, v2, v3;
	float		d;

	VectorSubtract( points[b].xyz, points[a].xyz, v1 );
	VectorSubtract( points[c].xyz, points[a].xyz, v2 );
	CrossProduct( v1, v2, v3 );
	d = VectorLength( v3 );

	// assume all very small or backwards triangles will cause problems
	if ( d < COLINEAR_AREA ) {
		return qtrue;
	}

	return qfalse;
}

/*
===============
SurfaceAsTriFan

The surface can't be represented as a single tristrip without
leaving a degenerate triangle (and therefore a crack), so add
a point in the middle and create (points-1) triangles in fan order
===============
*/
static void SurfaceAsTriFan( mapDrawSurface_t *ds, dsurface_t *out ) {
	int					i, j;
	int					colorSum[4];
	drawVertNew_t			*mid, *v;

	// create a new point in the center of the face
	if ( numDrawVerts == MAX_MAP_DRAW_VERTS ) {
		Error( "MAX_MAP_DRAW_VERTS" );
	}
	mid = &drawVerts[ numDrawVerts ];
	numDrawVerts++;

	VectorClear(mid->xyz);
	mid->st[0] = mid->st[1] = 0;

	colorSum[0] = colorSum[1] = colorSum[2] = colorSum[3] = 0;

	v = drawVerts + out->firstVert;
	for (i = 0 ; i < out->numVerts ; i++, v++ ) {
		VectorAdd( mid->xyz, v->xyz, mid->xyz );
		mid->st[0] += v->st[0];
		mid->st[1] += v->st[1];

		colorSum[0] += v->color[0];
		colorSum[1] += v->color[1];
		colorSum[2] += v->color[2];
		colorSum[3] += v->color[3];
	}

	mid->xyz[0] /= out->numVerts;
	mid->xyz[1] /= out->numVerts;
	mid->xyz[2] /= out->numVerts;

	mid->st[0] /= out->numVerts;
	mid->st[1] /= out->numVerts;

	mid->color[0] = colorSum[0] / out->numVerts;
	mid->color[1] = colorSum[1] / out->numVerts;
	mid->color[2] = colorSum[2] / out->numVerts;
	mid->color[3] = colorSum[3] / out->numVerts;

	VectorCopy((drawVerts+out->firstVert)->normal, mid->normal );

	// fill in indices in trifan order
	ds->numIndexes = out->numVerts*3;
	ds->indexes = malloc(ds->numIndexes * sizeof(int));

	for ( i = 0, j = 0 ; i < out->numVerts ; i++ ) {
		ds->indexes[j++] = out->numVerts;
		ds->indexes[j++] = i;
		ds->indexes[j++] = (i+1) % out->numVerts;
	}

	EmitDrawIndexes(ds, out);

	out->numVerts++;
}


/*
================
SurfaceAsTristrip

Try to create indices that make (points-2) triangles in tristrip order
================
*/
static void SurfaceAsTristrip( mapDrawSurface_t *ds, dsurface_t *out ) {
	int					i;
	int					rotate;
	int					numIndices;
	int					ni;
	int					a, b, c;
	int					indices[SHADER_MAX_INDEXES];

	// determine the triangle strip order
	numIndices = ( out->numVerts - 2 ) * 3;
	if ( numIndices > SHADER_MAX_INDEXES ) {
		Error( "SHADER_MAX_INDEXES exceeded for surface" );
	}

	// try all possible orderings of the points looking
	// for a strip order that isn't degenerate
	for ( rotate = 0 ; rotate < out->numVerts ; rotate++ ) {
		for ( ni = 0, i = 0 ; i < out->numVerts - 2 - i ; i++ ) {
			a = ( out->numVerts - 1 - i + rotate ) % out->numVerts;
			b = ( i + rotate ) % out->numVerts;
			c = ( out->numVerts - 2 - i + rotate ) % out->numVerts;

			if ( IsTriangleDegenerate( drawVerts + out->firstVert, a, b, c ) ) {
				break;
			}
			indices[ni++] = a;
			indices[ni++] = b;
			indices[ni++] = c;

			if ( i + 1 != out->numVerts - 1 - i ) {
				a = ( out->numVerts - 2 - i + rotate ) % out->numVerts;
				b = ( i + rotate ) % out->numVerts;
				c = ( i + 1 + rotate ) % out->numVerts;

				if ( IsTriangleDegenerate( drawVerts + out->firstVert, a, b, c ) ) {
					break;
				}
				indices[ni++] = a;
				indices[ni++] = b;
				indices[ni++] = c;
			}
		}
		if ( ni == numIndices ) {
			break;		// got it done without degenerate triangles
		}
	}

	// if any triangle in the strip is degenerate,
	// render from a centered fan point instead
	if ( ni < numIndices ) {
		c_fanSurfaces++;
		SurfaceAsTriFan( ds, out );
		return;
	}

	// a normal tristrip
	c_stripSurfaces++;

	ds->numIndexes = ni;
	ds->indexes = indices;

	EmitDrawIndexes(ds, out);

	ds->indexes = NULL;
}

/*
===============
EmitPlanarSurf
===============
*/
void EmitPlanarSurf( mapDrawSurface_t *ds ) {
	int				j;
	dsurface_t		*out;
	drawVertNew_t		*outv;

	if ( numDrawSurfaces == MAX_MAP_DRAW_SURFS ) {
		Error( "MAX_MAP_DRAW_SURFS" );
	}
	out = &drawSurfaces[ numDrawSurfaces ];
	numDrawSurfaces++;

	out->surfaceType = MST_PLANAR;
	out->shaderNum = EmitShader( ds->shaderInfo->shader );
//	out->planeNum = ds->planeNum;
	out->planeNum = EmitPlane(ds->planeNum);
	out->firstVert = numDrawVerts;
	out->numVerts = ds->numVerts;

	out->firstFacePlane = -1;

	out->firstSurfacePlane = out->firstSurfaceFacet = -1;
	out->numSurfacePlanes = out->numSurfaceFacets = 0;
	out->firstFoliage = -1;
	out->numFoliages = 0;

	for ( j = 0 ; j < ds->numVerts ; j++ ) {
		if ( numDrawVerts == MAX_MAP_DRAW_VERTS ) {
			Error( "MAX_MAP_DRAW_VERTS" );
		}
		outv = &drawVerts[ numDrawVerts ];
		numDrawVerts++;
//		memcpy( outv, &ds->verts[ j ], sizeof( *outv ) );

		outv->xyz[0] = ds->verts[j].xyz[0];
		outv->xyz[1] = ds->verts[j].xyz[1];
		outv->xyz[2] = ds->verts[j].xyz[2];
		outv->normal[0] = ds->verts[j].normal[0];
		outv->normal[1] = ds->verts[j].normal[1];
		outv->normal[2] = ds->verts[j].normal[2];
		outv->st[0] = ds->verts[j].st[0];
		outv->st[1] = ds->verts[j].st[1];

		outv->color[0] = 255;
		outv->color[1] = 255;
		outv->color[2] = 255;
		outv->color[3] = 255;
	}

	// create the indexes
	SurfaceAsTristrip( ds, out );

	// Compute bounds
	CalcSurfaceBounds(out);
	DeformSurfaceBounds(out, ds->shaderInfo->deform, ds->shaderInfo->deformSize);

	// Compute tangent vectors
	CalcSurfaceTangentVectors(out->numIndexes, &drawIndexes[out->firstIndex], out->numVerts, &drawVerts[out->firstVert]);

	if (out->numIndexes > SHADER_MAX_INDEXES || out->numVerts > SHADER_MAX_VERTEXES)
		Error("SHADER_MAX_INDEXES or SHADER_MAX_VERTEXES hit by surface with shader %s", ds->shaderInfo->shader);

	// Add foliage for this surface
	AddFoliageToSurface(out, ds->shaderInfo);
}


/*
===============
EmitPatchSurf
===============
*/
void EmitPatchSurf( mapDrawSurface_t *ds ) {
	dsurface_t		*out;

	if ( numDrawSurfaces == MAX_MAP_DRAW_SURFS ) {
		Error( "MAX_MAP_DRAW_SURFS" );
	}
	out = &drawSurfaces[ numDrawSurfaces ];
	numDrawSurfaces++;

	out->surfaceType = MST_PATCH;
	out->shaderNum = EmitShader( ds->shaderInfo->shader );
	out->planeNum = -1;
	out->firstVert = numDrawVerts;
//	out->numVerts = ds->numVerts;
	out->firstIndex = numDrawIndexes;
//	out->numIndexes = ds->numIndexes;

	out->firstFoliage = -1;
	out->numFoliages = 0;

	// Generate and emit the collision info
	EmitPatchCollideForPatchSurface(ds, out);

	// Generate the render geometry
	PatchDrawSurfaceFromGrid(out, ds);

	// Emit indices
	EmitDrawIndexes(ds, out);

	// Compute face planes
	out->firstFacePlane = numFacePlanes;

	if (numFacePlanes + out->numIndexes/3 > MAX_MAP_DRAW_FACEPLANES)
		Error("MAX_MAP_DRAW_FACEPLANES");

	CalcSurfaceFacePlanes(out->numIndexes / 3, &drawIndexes[out->firstIndex], &facePlanes[out->firstFacePlane], &drawVerts[out->firstVert]);
	numFacePlanes += out->numIndexes / 3;

	// Compute bounds
	CalcSurfaceBounds(out);
	DeformSurfaceBounds(out, ds->shaderInfo->deform, ds->shaderInfo->deformSize);

	// Compute tangent vectors
	CalcSurfaceTangentVectors(out->numIndexes, &drawIndexes[out->firstIndex], out->numVerts, &drawVerts[out->firstVert]);

	if (out->numIndexes > SHADER_MAX_INDEXES || out->numVerts > SHADER_MAX_VERTEXES)
		Error("SHADER_MAX_INDEXES or SHADER_MAX_VERTEXES hit by surface with shader %s", ds->shaderInfo->shader);

	// Add foliage for this surface
	AddFoliageToSurface(out, ds->shaderInfo);
}

/*
===============
EmitModelSurf
===============
*/
void EmitModelSurf( mapDrawSurface_t *ds ) {
	int				j;
	dsurface_t		*out;
	drawVertNew_t		*outv;

	if ( numDrawSurfaces == MAX_MAP_DRAW_SURFS ) {
		Error( "MAX_MAP_DRAW_SURFS" );
	}
	out = &drawSurfaces[ numDrawSurfaces ];
	numDrawSurfaces++;

	out->surfaceType = MST_TRIANGLE_SOUP;
	out->shaderNum = EmitShader( ds->shaderInfo->shader );
	out->planeNum = -1;
	out->firstVert = numDrawVerts;
	out->numVerts = ds->numVerts;
	out->firstIndex = numDrawIndexes;
	out->numIndexes = ds->numIndexes;

	out->firstFoliage = -1;
	out->numFoliages = 0;

	// Generate and emit the collision info
	EmitTriangleCollideForTriangleSurface(ds, out);

	// Generate the render geometry
	for ( j = 0 ; j < ds->numVerts ; j++ ) {
		if ( numDrawVerts == MAX_MAP_DRAW_VERTS ) {
			Error( "MAX_MAP_DRAW_VERTS" );
		}
		outv = &drawVerts[ numDrawVerts ];
		numDrawVerts++;
//		memcpy( outv, &ds->verts[ j ], sizeof( *outv ) );

		outv->xyz[0] = ds->verts[j].xyz[0];
		outv->xyz[1] = ds->verts[j].xyz[1];
		outv->xyz[2] = ds->verts[j].xyz[2];
		outv->normal[0] = ds->verts[j].normal[0];
		outv->normal[1] = ds->verts[j].normal[1];
		outv->normal[2] = ds->verts[j].normal[2];
		outv->st[0] = ds->verts[j].st[0];
		outv->st[1] = ds->verts[j].st[1];
		outv->color[0] = ds->verts[j].color[0];
		outv->color[1] = ds->verts[j].color[1];
		outv->color[2] = ds->verts[j].color[2];
		outv->color[3] = ds->verts[j].color[3];

		if (ds->terrain){
			outv->tangents[0][0] = ds->verts[j].tangents[0][0];
			outv->tangents[0][1] = ds->verts[j].tangents[0][1];
			outv->tangents[0][2] = ds->verts[j].tangents[0][2];
			outv->tangents[1][0] = ds->verts[j].tangents[1][0];
			outv->tangents[1][1] = ds->verts[j].tangents[1][1];
			outv->tangents[1][2] = ds->verts[j].tangents[1][2];
		}
	}

	// Emit indices
	EmitDrawIndexes(ds, out);

	// Compute face planes
	out->firstFacePlane = numFacePlanes;

	if (numFacePlanes + out->numIndexes/3 > MAX_MAP_DRAW_FACEPLANES)
		Error("MAX_MAP_DRAW_FACEPLANES");

	CalcSurfaceFacePlanes(out->numIndexes / 3, &drawIndexes[out->firstIndex], &facePlanes[out->firstFacePlane], &drawVerts[out->firstVert]);
	numFacePlanes += out->numIndexes / 3;

	// Compute bounds
	CalcSurfaceBounds(out);
	DeformSurfaceBounds(out, ds->shaderInfo->deform, ds->shaderInfo->deformSize);

	// Compute tangent vectors
	if (!ds->terrain)
		CalcSurfaceTangentVectors(out->numIndexes, &drawIndexes[out->firstIndex], out->numVerts, &drawVerts[out->firstVert]);

	if (out->numIndexes > SHADER_MAX_INDEXES || out->numVerts > SHADER_MAX_VERTEXES)
		Error("SHADER_MAX_INDEXES or SHADER_MAX_VERTEXES hit by surface with shader %s", ds->shaderInfo->shader);

	// Add foliage for this surface
	AddFoliageToSurface(out, ds->shaderInfo);
}

/*
===============
EmitFoliageSurf
===============
*/
void EmitFoliageSurf (mapDrawSurface_t *ds){

	dsurface_t			*out;
	dfoliage_t			*f;
	drawVertNew_t		*vert;
	vec3_t				point, axis[3];
	int					i, j;

	if (numDrawSurfaces == MAX_MAP_DRAW_SURFS)
		Error("MAX_MAP_DRAW_SURFS");

	out = &drawSurfaces[numDrawSurfaces++];

	out->surfaceType = MST_FOLIAGE;
	out->shaderNum = ds->foliageShader;
	out->planeNum = -1;

	out->firstSurfacePlane = out->firstSurfaceFacet = -1;
	out->numSurfacePlanes = out->numSurfaceFacets = 0;

	out->firstIndex = ds->foliageIndex;
	out->numIndexes = ds->numIndexes;

	out->firstVert = ds->foliageVertex;
	out->numVerts = ds->numVerts;

	out->firstNeighbor = ds->foliageNeighbor;
	out->firstFacePlane = ds->foliageFacePlane;

	out->firstFoliage = ds->firstFoliage;
	out->numFoliages = ds->numFoliages;

	out->foliageRadius = ds->foliageRadius;
	out->foliageMinDistance = ds->foliageMinDistance;
	out->foliageMaxDistance = ds->foliageMaxDistance;

	// Set mins/maxs for culling
	ClearBounds(out->mins, out->maxs);

	for (i = 0; i < ds->numFoliages; i++){
		f = &foliages[ds->firstFoliage+i];

		AnglesToAxis(f->angles, axis);

		vert = &drawVerts[ds->foliageVertex];
		for (j = 0; j < ds->numVerts; j++, vert++){
			point[0] = DotProduct(vert->xyz, axis[0]) + f->origin[0];
			point[1] = DotProduct(vert->xyz, axis[1]) + f->origin[1];
			point[2] = DotProduct(vert->xyz, axis[2]) + f->origin[2];

			AddPointToBounds(point, out->mins, out->maxs);
		}
	}

	DeformSurfaceBounds(out, ds->shaderInfo->deform, ds->shaderInfo->deformSize);
}


//======================================================================

/*
=====================
FilterDrawsurfsIntoTree

Upon completion, all drawsurfs that actually generate a reference
will have been emited to the bspfile arrays, and the references
will have valid final indexes
=====================
*/
void FilterDrawsurfsIntoTree( entity_t *e, tree_t *tree ) {
	int				i;
	mapDrawSurface_t	*ds;
	int				refs;
	int				c_surfs, c_refs;

	qprintf( "----- FilterDrawsurfsIntoTree -----\n");

	c_surfs = 0;
	c_refs = 0;
	for ( i = e->firstDrawSurf ; i < numMapDrawSurfs ; i++ ) {
		ds = &mapDrawSurfs[i];

		if ( !ds->numVerts && !ds->flareSurface ) {
			continue;
		}
		if ( ds->miscModel ) {
			refs = FilterMiscModelSurfIntoTree( ds, tree );
			EmitModelSurf( ds );		
		} else if ( ds->patch ) {
			refs = FilterPatchSurfIntoTree( ds, tree );
			EmitPatchSurf( ds );		
		} else if ( ds->foliage ) {
			refs = FilterFoliageSurfIntoTree( ds, tree );
			EmitFoliageSurf( ds );
		} else {
			refs = FilterFaceIntoTree( ds, tree );
			EmitPlanarSurf( ds );		
		}

		// Ugly hack for culling
		if (ds->shaderInfo->deform != DFRM_NONE){
			dsurface_t	*surf;

			surf = &drawSurfaces[numDrawSurfaces - 1];

			refs += FilterDrawSurfBoundsIntoTree(surf->mins, surf->maxs, ds, tree->headnode);
		}

		if ( refs > 0 ) {
			c_surfs++;
			c_refs += refs;
		}
	}
	qprintf( "%5i emited drawsurfs\n", c_surfs );
	qprintf( "%5i references\n", c_refs );
	qprintf( "%5i stripfaces\n", c_stripSurfaces );
	qprintf( "%5i fanfaces\n", c_fanSurfaces );
}



